/*
 * @Author: szx
 * @Date: 2021-11-24 09:52:39
 * @LastEditTime: 2021-11-24 10:34:58
 * @Description:
 * @FilePath: \leetcode\300-399\300\300.js
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
// dp[i] 严格比目前值小的
// var lengthOfLIS = function (nums) {
//     const n = nums.length;
//     const dp = new Array(n).fill(1);
//     for (let i = 0; i < n; i++) {
//         let max = 0;
//         for (let j = i; j >= 0; j--) {
//             if (nums[j] < nums[i]) {
//                 max = Math.max(dp[j], max);
//             }
//         }
//         dp[i] += max;
//     }
//     return Math.max.apply(null, dp);
// };

// d[i] ，表示长度为 i的最长上升子序列的末尾元素的最小值，
// 用 len 记录目前最长上升子序列的长度
var lengthOfLIS = function (nums) {
    const n = nums.length;
    if (n == 0) {
        return 0;
    }
    let len = 1;

    const d = new Array(n + 1).fill(0);
    d[len] = nums[0];
    for (let i = 1; i < n; ++i) {
        if (nums[i] > d[len]) {
            d[++len] = nums[i];
        } else {
            let l = 1,
                r = len,
                pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
            while (l <= r) {
                let mid = (l + r) >> 1;
                if (d[mid] < nums[i]) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            d[pos + 1] = nums[i];
        }
    }
    return len;
};

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));
